package LearnDataStructure.c_树结构;

import java.util.List;
import java.util.function.Consumer;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-07 21:57
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构
 */
public interface MyBinarySearchTreeAPI<K, V> {

    /**
     * 添加节点
     * @param key
     * @param value
     * @return
     */
    BSTNode<K, V> insert(K key, V value);

    /**
     * 删除节点
     * @param key
     */
    void remove(K key);

    /**
     * 获取key的value
     * @param key
     * @return
     */
    BSTNode<K,V> getValue(K key);

    /**
     * 获取仅仅比key小的最近的key
     * @param key
     * @return
     */
    K predecessor(K key);

    /**
     * 获取仅仅比key大的最近的key
     * 1、是其右子树的最小值
     * 2、没有右子树，则向上追溯，直到某个祖先节点是左孩子，返回这个祖先节点的父节点，它就是x的后继
     * @param key
     * @return
     */
    K successor(K key);

    /**
     * 获取最小key
     * @return
     */
    K min();

    /**
     * 获取最大key
     * @return
     */
    K max();

    /**
     * 检查当前二叉搜索树是否平衡
     * @return
     */
    boolean isBalance();

    /**
     * 返回树中元素数
     * @return
     */
    int getSize();

    /**
     * 返回树高
     * @return
     */
    int getHeight();

    /**
     * 中序遍历
     * 左根右
     * @param node list
     */
    void inOrder(BSTNode<K, V> node, List<BSTNode<K, V>> list);

    /**
     * 层级遍历
     * @return
     */
    List<List<BSTNode<K, V>>> levelOrder();
}
